#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#include "imbus_internal.h"
#include "im_slist.h"

#define _im_slist_alloc()               im_slice_new (IMSList)
#define _im_slist_alloc0()              im_slice_new0 (IMSList)
#define _im_slist_free_node(slist)      im_slice_delete (IMSList, slist)

/****************************** Public functions **************************/
IMSList *
im_slist_alloc (void)
{
    return _im_slist_alloc0 ();
}

void
im_slist_free (IMSList *slist)
{
    IMSList *next;

    while (slist) {
        next = slist->next;
        _im_slist_free_node (slist);
        slist = next;
    }
}

void
im_slist_free_node (IMSList *slist)
{
    _im_slist_free_node (slist);
}

IMSList *
im_slist_append (IMSList *list, IMPointer data)
{
    IMSList *new_list;
    IMSList *last;

    new_list = _im_slist_alloc ();
    new_list->data = data;
    new_list->next = 0;

    if (list) {
        last = im_slist_last (list);
        /* _im_assert (last != 0); */
        last->next = new_list;

        return list;
    } else
        return new_list;
}

IMSList *
im_slist_prepend (IMSList *list, IMPointer data)
{
    IMSList *new_list;

    new_list = _im_slist_alloc ();
    new_list->data = data;
    new_list->next = list;

    return new_list;
}

IMSList *
im_slist_insert (IMSList *list, IMPointer data, IMInt position)
{
    IMSList *prev_list;
    IMSList *tmp_list;
    IMSList *new_list;

    if (position < 0)
        return im_slist_append (list, data);
    else if (position == 0)
        return im_slist_prepend (list, data);

    new_list = _im_slist_alloc ();
    new_list->data = data;

    if (!list) {
        new_list->next = 0;
        return new_list;
    }

    prev_list = 0;
    tmp_list = list;

    while ((position-- > 0) && tmp_list) {
        prev_list = tmp_list;
        tmp_list = tmp_list->next;
    }

    if (prev_list) {
        new_list->next = prev_list->next;
        prev_list->next = new_list;
    } else {
        new_list->next = list;
        list = new_list;
    }

    return list;
}

IMSList *
im_slist_insert_before (IMSList *slist, IMSList *sibling, IMPointer data)
{
    if (!slist) {
        slist = _im_slist_alloc ();
        slist->data = data;
        slist->next = 0;
        _im_return_val_if_fail (sibling == 0, slist);
        return slist;
    } else {
        IMSList *node, *last = 0;

        for (node = slist; node; last = node, node = last->next)
            if (node == sibling)
                break;
        if (!last) {
            node = _im_slist_alloc ();
            node->data = data;
            node->next = slist;

            return node;
        } else {
            node = _im_slist_alloc ();
            node->data = data;
            node->next = last->next;
            last->next = node;

            return slist;
        }
    }
}

IMSList *
im_slist_concat (IMSList *list1, IMSList *list2)
{
    if (list2) {
        if (list1)
            im_slist_last (list1)->next = list2;
        else
            list1 = list2;
    }

    return list1;
}

IMSList *
im_slist_remove (IMSList *list, IMConstPointer data)
{
    IMSList *tmp, *prev = 0;

    tmp = list;
    while (tmp) {
        if (tmp->data == data) {
            if (prev)
                prev->next = tmp->next;
            else
                list = tmp->next;

            im_slist_free_node (tmp);
            break;
        }
        prev = tmp;
        tmp = prev->next;
    }

    return list;
}

IMSList *
im_slist_remove_all (IMSList *list, IMConstPointer data)
{
    IMSList *tmp, *prev = 0;

    tmp = list;
    while (tmp) {
        if (tmp->data == data) {
            IMSList *next = tmp->next;

            if (prev)
                prev->next = next;
            else
                list = next;

            im_slist_free_node (tmp);
            tmp = next;
        } else {
            prev = tmp;
            tmp = prev->next;
        }
    }

    return list;
}

static inline IMSList *
_im_slist_remove_link (IMSList *list, IMSList *link)
{
    IMSList *tmp;
    IMSList *prev;

    prev = 0;
    tmp = list;

    while (tmp) {
        if (tmp == link) {
            if (prev)
                prev->next = tmp->next;
            if (list == tmp)
                list = list->next;

            tmp->next = 0;
            break;
        }

        prev = tmp;
        tmp = tmp->next;
    }

    return list;
}

IMSList *
im_slist_remove_link (IMSList *list, IMSList *link)
{
    return _im_slist_remove_link (list, link);
}

IMSList *
im_slist_delete_link (IMSList *list, IMSList *link)
{
    list = _im_slist_remove_link (list, link);
    _im_slist_free_node (link);

    return list;
}

IMSList *
im_slist_clone (IMSList *list)
{
    IMSList *new_list = 0;

    if (list) {
        IMSList *last;

        new_list = _im_slist_alloc ();
        new_list->data = list->data;
        last = new_list;
        list = list->next;
        while (list) {
            last->next = _im_slist_alloc ();
            last = last->next;
            last->data = list->data;
            list = list->next;
        }
        last->next = 0;
    }

    return new_list;
}

IMSList *
im_slist_reverse (IMSList *list)
{
    IMSList *prev = 0;

    while (list) {
        IMSList *next = list->next;

        list->next = prev;

        prev = list;
        list = next;
    }

    return prev;
}

IMSList *
im_slist_nth (IMSList *list, IMUInt n)
{
    while (n-- > 0 && list)
        list = list->next;

    return list;
}

IMPointer
im_slist_nth_data (IMSList *list, IMUInt n)
{
    while (n-- > 0 && list)
        list = list->next;

    return list ? list->data : 0;
}

IMSList *
im_slist_find (IMSList *list, IMConstPointer data)
{
    while (list) {
        if (list->data == data)
            break;
        list = list->next;
    }

    return list;
}

IMSList *
im_slist_find_custom (IMSList *list, IMConstPointer data, IMCompareFunc func)
{
    _im_return_val_if_fail (func != 0, list);

    while (list) {
        if (!func (list->data, data))
            return list;
        list = list->next;
    }

    return 0;
}

IMInt
im_slist_position (IMSList *list, IMSList *link)
{
    IMInt i;

    i = 0;
    while (list) {
        if (list == link)
            return i;
        i++;
        list = list->next;
    }

    return -1;
}

IMInt
im_slist_index (IMSList *list, IMConstPointer data)
{
    IMInt i;

    i = 0;
    while (list) {
        if (list->data == data)
            return i;
        i++;
        list = list->next;
    }

    return -1;
}

IMSList *
im_slist_last (IMSList *list)
{
    if (list) {
        while (list->next)
            list = list->next;
    }

    return list;
}

IMUInt
im_slist_length (IMSList *list)
{
    IMUInt length;

    length = 0;
    while (list) {
        length++;
        list = list->next;
    }

    return length;
}

void
im_slist_foreach (IMSList *list, IMFunc func, IMPointer user_data)
{
    while (list) {
        IMSList *next = list->next;
        (*func) (list->data, user_data);
        list = next;
    }
}

static IMSList *
im_slist_insert_sorted_real (IMSList *list,
                             IMPointer data, IMFunc func, IMPointer user_data)
{
    IMSList *tmp_list = list;
    IMSList *prev_list = 0;
    IMSList *new_list;
    IMInt cmp;

    _im_return_val_if_fail (func != 0, list);

    if (!list) {
        new_list = _im_slist_alloc ();
        new_list->data = data;
        new_list->next = 0;
        return new_list;
    }

    cmp = ((IMCompareDataFunc) func) (data, tmp_list->data, user_data);

    while ((tmp_list->next) && (cmp > 0)) {
        prev_list = tmp_list;
        tmp_list = tmp_list->next;

        cmp = ((IMCompareDataFunc) func) (data, tmp_list->data, user_data);
    }

    new_list = _im_slist_alloc ();
    new_list->data = data;

    if ((!tmp_list->next) && (cmp > 0)) {
        tmp_list->next = new_list;
        new_list->next = 0;
        return list;
    }

    if (prev_list) {
        prev_list->next = new_list;
        new_list->next = tmp_list;
        return list;
    } else {
        new_list->next = list;
        return new_list;
    }
}

IMSList *
im_slist_insert_sorted (IMSList *list, IMPointer data, IMCompareFunc func)
{
    return im_slist_insert_sorted_real (list, data, (IMFunc) func, 0);
}

IMSList *
im_slist_insert_sorted_with_data (IMSList *list,
                                  IMPointer data,
                                  IMCompareDataFunc func, IMPointer user_data)
{
    return im_slist_insert_sorted_real (list, data, (IMFunc) func, user_data);
}

static IMSList *
im_slist_sort_merge (IMSList *l1,
                     IMSList *l2, IMFunc compare_func, IMPointer user_data)
{
    IMSList list, *l;
    IMInt cmp;

    l = &list;

    while (l1 && l2) {
        cmp =
            ((IMCompareDataFunc) compare_func) (l1->data, l2->data,
                                                user_data);

        if (cmp <= 0) {
            l = l->next = l1;
            l1 = l1->next;
        } else {
            l = l->next = l2;
            l2 = l2->next;
        }
    }
    l->next = l1 ? l1 : l2;

    return list.next;
}

static IMSList *
im_slist_sort_real (IMSList *list, IMFunc compare_func, IMPointer user_data)
{
    IMSList *l1, *l2;

    if (!list)
        return 0;
    if (!list->next)
        return list;

    l1 = list;
    l2 = list->next;

    while ((l2 = l2->next) != 0) {
        if ((l2 = l2->next) == 0)
            break;
        l1 = l1->next;
    }
    l2 = l1->next;
    l1->next = 0;

    return
        im_slist_sort_merge (im_slist_sort_real
                             (list, compare_func, user_data),
                             im_slist_sort_real (l2, compare_func, user_data),
                             compare_func, user_data);
}

IMSList *
im_slist_sort (IMSList *list, IMCompareFunc compare_func)
{
    return im_slist_sort_real (list, (IMFunc) compare_func, 0);
}

IMSList *
im_slist_sort_with_data (IMSList *list,
                         IMCompareDataFunc compare_func, IMPointer user_data)
{
    return im_slist_sort_real (list, (IMFunc) compare_func, user_data);
}

/*
vi:ts=4:nowrap:ai:expandtab
*/
